#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <cstring>

void InsertSort(int* a, int n)
{
    for(int i = 0; i < n - 1; i++)
    {
        int end = i;
        int tmp = a[end+1];

        while(end >= 0)
        {
            if(tmp < a[end])
            {
                a[end + 1] = a[end];
                end--;
            }
            else
            {
                break;
            }
        }
        a[end + 1] = tmp;
    }
}

void ShellSort(int* a, int n)
{
    int gap = n;
    while(gap > 1)
    {
        gap = gap / 2;
        for(int i = 0; i < n - gap; i++)
        {
            int end = i;
            int tmp = a[end + gap];
            while(end >= 0)
            {
                if(tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap; 
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}

void Swap(int* x, int* y)
{
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

// void SelectSort(int* a, int n)
// {
//     for(int i = 0; i < n; i++)
//     {
//         int start = i;
//         int min = start;
//         while(start < n)
//         {
//             if(a[start] < a[min])
//                 min = start;
//             start++;
//         }
//         Swap(&a[i], &a[min]);
//     }
// }

void SelectSort(int* a, int n)
{
    int left = 0;
    int right = n - 1;
    while(left < right)
    {
        int minIndex = left;
        int maxIndex = left;

        for(int i = left; i <= right; i++)
        {
            if(a[i] < a[minIndex])
                minIndex = i;
            if(a[i] > a[maxIndex])
                maxIndex = i;
        }

        Swap(&a[minIndex], &a[left]);
        if(left == maxIndex)
        {
            maxIndex = minIndex;
        }
        Swap(&a[maxIndex], &a[right]);
        left++;
        right--;
    }
}

void AdjustDown(int* a, int n, int parent)
{
    int child = parent * 2 + 1;

    while(child < n)
    {
        if(child + 1 < n && a[child + 1] < a[child])
        {
            child++;
        }
        if(a[child] < a[parent])
        {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}


void StackSort(int* a, int n)
{
    for(int i = (n-1-1) / 2; i >= 0; i--)
    {
        AdjustDown(a, n, i);
    }

    int end = n - 1;
    while(end)
    {
        Swap(&a[0], &a[end]);
        AdjustDown(a, end, 0);
        end--;
    }
}

void BubbleSort(int* a, int n)
{
    int end = 0;
    for(end = n - 1; end >= 0; end--)
    {
        int exchange = 0;
        for(int i = 0; i < end; i++)
        {
            if(a[i] > a[i+1])
            {
                Swap(&a[i], &a[i+1]);
                exchange = 1;
            }
        }
        if(exchange = 0)
            break;
    }
}


void QuickSort1(int* a, int begin, int end)
{
    if(begin >= end)
        return;
    
    int left = begin;
    int right = end;
    int keyi = left;
    while(left < right)
    {
        while(left < right && a[right] >= a[keyi])
        {
            right--;
        }

        while(left < right && a[left] <= a[keyi])
        {
            left++;
        }

        if(left < right)
        {
            Swap(&a[left], &a[right]);
        }
    }
    int meeti = left;
    Swap(&a[keyi], &a[meeti]);

    QuickSort1(a, begin, meeti-1);
    QuickSort1(a,  meeti+1, end);
}

void QuickSort2(int* a, int begin, int end)
{
    if(begin >= end)
        return;

    int left = begin;
    int right = end;
    int key = a[left];
    while(left < right)
    {
        while(left < right && a[right] >= key)
        {
            right--;
        } 

        a[left] = a[right];
        
        while(left < right && a[left] <= key)
        {
            left++;
        }
        a[right] = a[left];
    }

    int meeti = left;
    a[meeti] = key;
    QuickSort2(a, begin, meeti - 1);
    QuickSort2(a, meeti + 1, end);
}

//三数取中;
int GetMidIndex(int* a, int left, int right)
{
    int mid = left + (right - left) / 2;

    if(a[mid] > a[left])
    {
        if(a[mid] < a[right])
            return mid;
        else if(a[left] > a[right])
            return left;
        else
            return right;
    }
}

void QuickSort3(int* a, int begin, int end)
{
    if(begin >= end)
        return;

    int minIndex = GetMidIndex(a, begin, end);
    Swap(&a[begin], &a[minIndex]);

    int prev = begin;
    int cur = begin + 1;
    int keyi = begin;
    while(cur <= end)
    {
        if(a[cur] < a[keyi] && ++prev != cur)
        {
            Swap(&a[prev], &a[cur]);
        }
        cur++;
    }

    int meeti = prev;
    Swap(&a[keyi], &a[meeti]);

    QuickSort3(a, begin, meeti-1);
    QuickSort3(a, meeti + 1, end);
}

void _MergeSort(int* a, int left, int right, int* tmp)
{
    if(left >= right)
        return;
    
    int mid = left + (right - left) / 2;
    _MergeSort(a, left, mid, tmp);
    _MergeSort(a, mid+1, right, tmp);
    int begin1 = left, end1 = mid;
    int begin2 = mid + 1, end2 = right;

    int i = left;
    while(begin1 <= end1 && begin2 <= end2)
    {
        if(a[begin1] < a[begin2])
            tmp[i++] = a[begin1++];
        else
            tmp[i++] = a[begin2++];
    }

    while(begin1 <= end1)
        tmp[i++] = a[begin1++];
    
    while(begin2 <= end2)
        tmp[i++] = a[begin2++];
    
    for(int j = left; j <= right; j++)
        a[j] = tmp[j];

}

void MergeSort(int* a, int n)
{
    int* tmp = (int*)malloc(sizeof(int) * n);
    if(tmp == nullptr)
    {
        printf("malloc fail\n");
        exit(-1);
    }
    _MergeSort(a, 0, n - 1, tmp);
    free(tmp);
}

void CountSort(int* a, int n)
{
    int min = a[0];
    int max = a[0];

    for(int i = 0; i < n; i++)
    {
        if(a[i] < min)
            min = a[i];
        if(a[i] > max)
            max = a[i];
    }

    int range = max - min + 1;
    int* count = (int*)calloc(range, sizeof(int));
    if(count == nullptr)
    {
        printf("malloc fail!");
        exit(-1);
    }

    for(int i = 0; i < n; i++)
    {
        count[a[i] - min]++;
    }

    int i = 0;
    for(int j = 0; j < range; j++)
    {
        while(count[j]--)
        {
            a[i++] = j + min;
        }
    }
    free(count);
}